#include<cstdio>
#include <stdlib.h>

#define maxV 100
#define maxK 10

int var;
int n;
int m;
int k;
int vari[maxV][maxV][maxK];
int inv[maxV*maxV*maxV][3];
bool source[maxV];

bool edge[maxV][maxV];

bool readGraph(FILE* gf){

	for(int i = 0; i < maxV; i++){
		for(int j = 0; j < maxV; j++){
			edge[i][j] = false;
		}
	}

	printf("GRAFO! ");
	fscanf(gf, "%d", &n);
	printf("%d ", n);
	fscanf(gf, "%d", &m);
	printf("%d\n", m);
	int v, u;
	for(int i = 0; i < m; i++){
		fscanf(gf, "%d", &v);
		fscanf(gf, "%d", &u);
		printf("%d %d \n", v,u);
		edge[v-1][u-1] = true;
		edge[u-1][v-1] = true;
	}

	return true;
}

bool createVar(){
	for(int i = 0; i < n; i++){
		source[i] = true;
		for(int j = 0; j < i; j++){
			if(!edge[j][i]) source[i] = false;
		}
	}

	for(int i = 0; i < n; i++){
		for(int l = 0; l < k; l++){
			if(!source[i]){
				vari[i][i][l] = var;
				inv[var][0] = i;
				inv[var][1] = i;
				inv[var][2] = l;
				var++;
			}
		}
	}

	for(int i = 0; i < n; i++){
		for(int j = i+1; j < n; j++){
			for(int l = 0; l < k; l++){
				if(!edge[i][j]){
					vari[i][j][l] = var;
					inv[var][0] = i;
					inv[var][1] = j;
					inv[var][2] = l;
					var++;
				}
			}
		}
	}

	return true;
}

bool writeNegRest(FILE* out, int v){
	for(int l = 0; l < k; l++){
		fprintf(out,"+1x%d", vari[v][v][l]+1);
		printf("+1x%d", vari[v][v][l]+1);
		for(int j = 0; j < v; j++){
			if(!edge[j][v]){
				fprintf(out,"+1x%d", vari[j][v][l]+1);
				printf("+1x%d", vari[j][v][l]+1);
			}
		}
	}

	fprintf(out," >= %d\n", k);
	printf(" >= %d\n", k);
	return true;
}

bool writeEdgeRest(FILE* out, int v, int u, int w){
	for(int l = 0; l < k; l++){
		fprintf(out,"+1x%d", vari[v][u][l]+1);
		printf("+1x%d", vari[v][u][l]+1);
		fprintf(out,"+1x%d", vari[v][w][l]+1);
		printf("+1x%d", vari[v][w][l]+1);
		if(!source[v]){
			fprintf(out,"-1x%d <= 0\n", vari[v][v][l]+1);
			printf("-1x%d <= 0\n", vari[v][v][l]+1);
		}
		else{
			fprintf(out," <= 1\n");
			printf(" <= 1\n");
		}
	}

	return true;
}

bool writeUmRest(FILE* out, int v, int u){
	for(int l = 0; l < k; l++){
		fprintf(out,"+1x%d", vari[v][u][l]+1);
		printf("+1x%d", vari[v][u][l]+1);
		if(!source[v]){
			fprintf(out,"-1x%d <= 0\n", vari[v][v][l]+1);
			printf("-1x%d <= 0\n", vari[v][v][l]+1);
		}
		else{
			fprintf(out," <= 1\n");
			printf(" <= 1\n");
		}
	}

	return true;
}

bool writeRelation(FILE* rel){
	fprintf(rel,"%d\n", var);
	printf("RELAÇÃO!\n");
	for(int i = 0; i < var; i++){
		fprintf(rel,"x%d x_{%d, %d}^{%d} \n", i+1, inv[i][0]+1, inv[i][1]+1, inv[i][2]+1);
		printf("x%d x_{%d, %d}^{%d} \n", i+1, inv[i][0]+1, inv[i][1]+1, inv[i][2]+1);
	}
	return true;
}

bool writeValid(FILE* out){
	for(int i = 0; i < var; i++){
		if(inv[i][0] == inv[i][1]) fprintf(out,"1 ");
		else fprintf(out,"0 ");
	}

	return true;
}

int main (int argc, char *argv[]){
	k = atoi(argv[1]);
	FILE* gf = fopen(argv[2], "r");
	FILE* out = fopen(argv[3], "w");
	FILE* rl = fopen(argv[4], "w");
	var = 0;
	readGraph(gf);
	createVar();

	fprintf(out, "DIM = %d\n", var);
	printf("DIM = %d\n", var);
	fprintf(out, "VALID\n");
	printf( "VALID\n");
	writeValid(out);
	fprintf(out,"\n");
	fprintf(out,"\n");
	printf("\n");


	fprintf(out,"LOWER_BOUNDS\n");
	printf("LOWER_BOUNDS\n");
	fprintf(out,"0");
	printf("0");
	for(long i = 1; i < var; i++){
		fprintf(out," 0");
		printf(" 0");
	}
	fprintf(out," \n");
	printf("\n");
	fprintf(out,"UPPER_BOUNDS\n");
	printf("UPPER_BOUNDS\n");
	fprintf(out,"1");
	printf("1");
	for(long i = 1; i < var; i++){
		fprintf(out," 1");
		printf(" 1");
	}
	fprintf(out,"\n");
	printf("\n");
	fprintf(out,"\n");
	printf("\n");

	fprintf(out,"ELIMINATION_ORDER\n");
	printf("ELIMINATION_ORDER\n");
	fprintf(out,"1");
	printf("1");
	for(int i = 1; i < var; i++){
		fprintf(out," %d", i+1);
		printf(" %d", i+1);
	}
	fprintf(out,"\n");
	printf("\n");
	fprintf(out,"\n");
	printf("\n");

	fprintf(out,"INEQUALITIES_SECTION\n");
	printf("INEQUALITIES_SECTION\n");
	for(int i = 0; i < n; i++){
		if(!source[i])writeNegRest(out, i);
		for(int j = i+1; j < n; j++){
			if(!edge[i][j])writeUmRest(out, i, j);
			for(int l = j+1; l < n; l++){
				if(!edge[i][j] && !edge[i][l] && edge[j][l]) writeEdgeRest(out, i, j, l);
			}
		}
	}
	fprintf(out,"\n");
	printf("\n");
	fprintf(out,"END");
	printf("END");

	writeRelation(rl);

	return 0;
}
